The presently disclosed subject matter relates to a method for controlling a check node of a decoder for decoding non-binary LDPC codes and to the corresponding check node.
LDPC (Low Density Parity Check) codes are known error-correcting codes for approaching Shannon's theoretical limit of transmission. Because of their performance in terms of noise immunity, LDPC codes, and in particular non-binary LDPC codes, find use in the field of transmitting and storing digital data.
Non-binary LDPC codes are constructed in a non-binary Galois field of order q, conventionally written as GF(q). An LDPC code in GF(q) is defined by a sparse parity matrix H of dimensions M×N, the elements of which belong to GF(q), N being the number of GF(q) elements in the code word and M being the number of parity constraints. For a Galois field GF(4) consisting of 4 elements {0, α0, α1, α2}, the parity matrix for N=6 and M=3, for example, is as follows:
  H  =      (                            0                                      α            0                                                α            0                                    0                                      α            2                                    0                                                  α            1                                    0                          0                                      α            0                                    0                                      α            2                                                            α            0                                    0                                      α            2                                    0                          0                                      α            1                                )  
This matrix can likewise be shown by a bipartite graph (Tanner graph) having N variable nodes receiving the symbols of the code word and M check nodes. Each column of the parity matrix is associated with a variable node and each line of the matrix is associated with a check node. In the case of a regular LDPC code, each check node is connected, by means of dc branches, to a single number dc of variable nodes. Similarly, each variable node is connected, by means of dv branches, to a single number dv of check nodes. In the case of a regular LDPC code, the number dc or dv of branches varies according to the variable node or check node.
The decoding of these LDPC codes is iterative and can include or can consist of exchanging messages via these branches, each variable or check node processing the messages received and, after processing, delivering other messages, as the case may be, to check nodes or variable nodes to which they are connected via branches. The exchanged messages represent probability density functions of the code symbols and are therefore in the form of vectors of size q. Such decoding is described in the document entitled “Decoding Algorithms for Non binary LDPC Codes Over GF(q)” by D. Declercq and M. Fossorier, Communications IEEE Transactions in Volume 55, Issue 4, April 2007, pages 633-643.
Some embodiments specifically relate to the method for controlling check nodes of the decoder. With reference to FIG. 1, each check node CN receives a plurality of incoming messages Ui and delivers outgoing messages Vj, with i,j∈[1 . . . dc], such that
      V    j    =            ∑              j        ≠        i              ⁢          U      i      
In the example of FIG. 1, the check node receives dc=4 incoming messages U1, U2, U3, U4 and delivers 4 outgoing messages V1, V2, V3, V4 such as:
  {                                                        V              1                        =                                          U                2                            +                              U                3                            +                              U                4                                                                                                    V              2                        =                                          U                1                            +                              U                3                            +                              U                4                                                                                                    V              3                        =                                          U                1                            +                              U                2                            +                              U                4                                                                                                    V              4                        =                                          U                1                            +                              U                2                            +                              U                3                                                             
wherein “+” is the addition operator in the Galois field GF(q).
Each incoming and outgoing message is a vector of size q, associating a probability density with each element of the Galois field. Each check node makes calculations on the incoming messages and delivers outgoing messages to the variable nodes.
Density probability functions are thus exchanged between the check nodes and the variable nodes, and conversely, until the code word has been completely decoded or a predefined number of iterations has been performed. Reference is then made to a “belief propagation” algorithm or BP algorithm.
Implementing such an algorithm is relatively complex and may require a high number of computations in the check node. With such algorithm, the complexity increases with the size of the GF(q). A straightforward implementation of the BP algorithm has a complexity of O(q2).
In order to reduce this complexity, it is known to work in the logarithmic field in order to convert the multiplications into additions. The data exchanged between nodes are log likelihood ratios (LLR).
To calculate the probability density functions of the outgoing message, another known solution for reducing the complexity can include or can consist of taking account solely of the nm greatest probability density functions in the incoming messages, nm<q. This algorithm, referred to as EMS (Extended Min-Sum), is described in detail in the document entitled “Algorithmes simplifiés pour le décodage de codes LDPC non binaires” de A. Voicila, D. Declercq, M. Fossorier et F. Verdier, GRETSI, Louvain-la-Neuve, Belgium, September 2005. This solution can be combined with the preceding solution such that the data exchanged are log likelihood ratios.
According to this algorithm, the incoming messages Ui are filtered and sorted prior to being processed by the check node. The messages supplied to the check node are then lists including only nm probability density function values or LLR sorted in descending order, each probability density function or LLR value being associated with an element of the Galois field GF(q). The number of probability function or LLR values taken into account by the check node being reduced (nm<q), the complexity of this algorithm is reduced but remains high nonetheless.
Currently, the EMS algorithm gives the best or better compromise between hardware complexity and communications performance.
But to achieve the required throughput of today's applications, executing the algorithms in software is not sufficient. Dedicated hardware architectures become mandatory. The largest complexity in the EMS algorithm is the computation of the Check Node (CN). State-of-the-art architectures apply a so called Forward-Backward (FWBW) scheme to process the check node. This architecture is disclosed in “Log-domain decoding of LDPC codes over GF(q)”, H. Wymeersch, H. Steendam, and M. Moeneclaey, Proc. IEEE International Conference on Communications, vol. 2, June 2004, pp. 772-776.
A serial calculation is carried out to reduce the hardware cost and to allow for reuse of intermediate results during the computation. However this scheme introduces high latency and degrades the throughput. This effect increases significantly when the size of the GF(q) grows.